package org.example.myleet.rosalind.gasm;

import org.example.myleet.rosalind.utils.DnaReverseComplementor;

import java.io.*;
import java.util.*;

public class Solution {
    /**
     * de Brujin图的节点
     */
    static class DBGNode {
        //下一个节点
        DBGNode next;

        //下一个节点k-mer本身
        String kMer;
        String prefix;
        String suffix;
        char head;
        public DBGNode(String kMer) {
            this.kMer = kMer;
            //de Brujin图的结点，首字母为此节点用于拼接序列用的字符，其后缀指向下一个前缀匹配的结点
            prefix = kMer.substring(0, kMer.length() - 1);
            suffix = kMer.substring(1);
            head = kMer.charAt(0);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("DBGNode{");
            sb.append("kMer='").append(kMer).append('\'');
            sb.append('}');
            return sb.toString();
        }
    }

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        //读取reads文件
        String path = solution.getClass().getResource("").getPath() + "example.txt";
//        System.out.println(path);
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String line;
        List<String> reads = new LinkedList<>();
        while (null != (line = br.readLine())) {
            line = line.trim();
            if (line.length() < 1) {
                break;
            }
            reads.add(line);
        }
//        System.out.println(reads);
        //根据题目意思，这些reads并没有给出其反向互补序列，因此需要将反向互补序列补出来
        List<String> dnaReads = new ArrayList<>(reads.size() * 2);
        for (String read : reads) {
            dnaReads.add(read);
            dnaReads.add(DnaReverseComplementor.reverseComplete(read));
        }
        //切割出k-mer
        int l = dnaReads.get(0).length();
        int k = l - 2; //example中reads的长度是5，为了产生奇数长度的k-mer，因此k取5-2=3，参考资料：https://zhuanlan.zhihu.com/p/84398195。
//        int k = l - 5; //数据集中reads的长度是50，为了产生奇数长度的k-mer，因此k取50-5=45。已测试过49长度的k-mer，不能拼接出结果
        DBGNode dbgNode = null;
        Map<String, DBGNode> prefixMapKMers = new HashMap<>(dnaReads.size() * (l - k + 1));
        for (String read : dnaReads) {
            for (int i = 0; i < read.length() - k + 1; ++i) {
                //切割出的k-mer做成一个de Brujin图的结点
                dbgNode = new DBGNode(read.substring(i, i + k));
                //以这个de Brujin图的节点的前缀做索引
                prefixMapKMers.put(dbgNode.prefix, dbgNode);
            }
        }
        //需要记录已经访问过的k-mer，如果再访问到这个k-mer，则说明序列拼接到达一个结束位置
        Set<String> visitedKMer = new HashSet<>(prefixMapKMers.size());
        //初始化，设置de Brujin图的头，并标记为访问过
        DBGNode head = dbgNode;
        prefixMapKMers.get(head.prefix);
        visitedKMer.add(head.kMer);
        DBGNode cur = dbgNode;
        while (cur != null) {
            //找下一个de Brujin结点
            DBGNode next = prefixMapKMers.get(cur.suffix);
            if (null != next) {
                //找到，从索引中移除
                prefixMapKMers.remove(cur.suffix);
            } else {
                //没找到，de Brujin创建过程结束
                break;
            }
            if (visitedKMer.contains(next.kMer)) {
                //访问到一个曾经出现的k-mer，de Brujin创建过程结束
                break;
            }
            //链接上一个结点
            visitedKMer.add(next.kMer);
            cur.next = next;
            cur = cur.next;
        }
        //输出结果，从de Brujin图的头开始一直访问到链表尾部，每次拼接节点代表的字符，即可得到完整序列
        StringBuilder result = new StringBuilder();
        cur = head;
        while (cur != null) {
            result.append(cur.head);
            cur = cur.next;
        }
        System.out.println(result);
    }
}
